package com.mojito.learn.algorithm.leetcode;

import com.mojito.learn.algorithm.datastructure.ListNode;
import com.mojito.learn.algorithm.datastructure.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author liufengqiang
 * @date 2021-07-05 10:30:20
 */
public class LeetCode2 {

    /**
     * 206. 反转链表
     */
    public ListNode reverseList(int type, ListNode head) {
        switch (type) {
            case 1:
                return reverseList1(head);
            case 2:
                return reverseList2(head);
            default:
                throw new RuntimeException();
        }
    }

    /**
     * 方法一：迭代：遍历链表时，将当前节点的next指向前一个节点（本来是指向后一个节点），事先存储前一个节点，并把后一个节点存起来
     * 时间复杂度：O(n)，空间复杂度：O(1)
     */
    private ListNode reverseList1(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    /**
     * 方法二：递归：比如[1,2,3,4,5]，循环到链表尾部，p指针指向5，head指针指向4，让4的next（即5）的next指向head（即4）完成反转，让head（即4）指向null
     * 回到递归上一层后head指向3，3指向4，4之前指向空了，所以head=[3,4]，让4指向3后，5是指向4的，所以p=[5,4,3]，直到结束
     * 时间复杂度：O(n)，空间复杂度：O(n)
     */
    private ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    /**
     * 226. 翻转二叉树
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    /**
     * 234. 回文链表
     */
    public boolean isPalindrome(ListNode head, int type) {
        switch (type) {
            case 1:
                return isPalindrome1(head);
            case 2:
                return isPalindrome2(head);
            case 3:
                return isPalindrome3(head);
            default:
                throw new RuntimeException();
        }
    }

    /**
     * 方法一：将数据复制到数组后，双指针遍历比较
     * 时间复杂度：O(n)，空间复杂度：O(n)
     */
    private boolean isPalindrome1(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        while (head != null) {
            vals.add(head.val);
            head = head.next;
        }

        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }

    private ListNode frontPointer;

    /**
     * 方法二：递归，通过递归反向遍历节点和正常节点比较，只要有一个不同即返回false
     * 时间复杂度：O(n)，空间复杂度：O(n)，栈深度n
     */
    private boolean isPalindrome2(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }

    private boolean recursivelyCheck(ListNode head) {
        if (head != null) {
            if (!recursivelyCheck(head.next)) {
                return false;
            }
            if (head.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    /**
     * 方法三：反转链表后半部分后和前半部分遍历比较
     * 步骤：1. 找到前半部分链表尾结点（快慢指针）；2. 反转后半部分链表；3. 遍历判断是否是回文；4. 恢复链表返回结果
     * 时间复杂度：O(n)，空间复杂度：O(1)
     */
    private boolean isPalindrome3(ListNode head) {
        if (head == null) {
            return true;
        }

        ListNode firstHalf = endOfFirstHalf(head);
        ListNode secondHalf = reverseList1(firstHalf.next);

        ListNode p1 = head;
        ListNode p2 = secondHalf;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        firstHalf.next = reverseList1(secondHalf);
        return result;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 279. 完全平方数
     */
    public int numSquares(int n) {
        // 解法一：动态规划
        // 解法二：贪心枚举
        // 解法三：贪心 + 广度优先搜索：将n减去比n小的所有平方数，直到n为0，此时层数即结果
        // 解法四：数学运算：四平方定理，4的k次幂 * (8m + 7)
        while (n % 4 == 0) {
            n /= 4;
        }
        if (n % 8 == 7) {
            return 4;
        }

        if (isSquare(n)) {
            return 1;
        }

        for (int i = 1; i * i <= n; ++i) {
            if (isSquare(n - i * i)) {
                return 2;
            }
        }
        return 3;
    }

    private boolean isSquare(int n) {
        int sq = (int) Math.sqrt(n);
        return n == sq * sq;
    }

    /**
     * 297. 二叉树的序列化与反序列化
     * 序列化
     */
    private String serialize(TreeNode root) {
        List<Integer> level = new ArrayList<>();
        if (root == null) {
            return level.toString();
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                TreeNode node = queue.poll();

                if (node == null) {
                    level.add(null);
                } else {
                    level.add(node.val);
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
            }
        }
        return level.toString();
    }

    /**
     * 297. 二叉树的序列化与反序列化
     * 反序列化
     */
    public TreeNode deserialize(String data) {
        if ("[]".equals(data)) {
            return null;
        }

        List<Integer> vals = Arrays.asList(data.substring(1, data.length() - 1).split(","))
                .stream().map(o -> "null".equals(o.trim()) ? null : Integer.valueOf(o.trim())).collect(Collectors.toList());
        TreeNode root = new TreeNode(vals.get(0));
        Queue<TreeNode> queue = new LinkedList<TreeNode>() {{
            add(root);
        }};

        int i = 1;
        while (!queue.isEmpty() && i < vals.size()) {
            TreeNode node = queue.poll();
            if (vals.get(i) != null) {
                node.left = new TreeNode(vals.get(i));
                queue.offer(node.left);
            }
            i++;
            if (vals.get(i) != null) {
                node.right = new TreeNode(vals.get(i));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}
